# -*- coding: utf-8 -*-            
# @Time : 2023/11/20 22:42
# @Author  : lining
# @FileName: 滑动窗口最大值.py
"""
https://leetcode.cn/problems/sliding-window-maximum/
懒惰删除法
给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回 滑动窗口中的最大值 。
输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]
（1）1，3，-1，最大值3   先建立大根堆
（2）3，-1，-3，最大值还是3   堆顶还是3，且3在窗口内，先不删除堆顶
（3）-1，-3，5 ，最大值5，3已经出界删除堆顶，
"""
import heapq # 默认小根堆
import queue


class Solution:
    def __init__(self, data, k):
        """
        :param data: 要滑动的数据
        :param k: 最大多少个数
        """
        self.data = data
        self.k = k

    def heap_large(self):
        """
        大根堆
        :param data: 传list
        :return:
        """
        # 存堆
        heap = []
        # 存结果
        result = []
        for a,b in enumerate(self.data):
            heapq.heappush(heap, [-b,a])
            if a >= self.k-1:
                max_value = heapq.heappop(heap)
                # 校验下标是否在边界内
                while max_value[1] <= a-self.k:
                    max_value = heapq.heappop(heap)
                result.append(-max_value[0])
                # 没有取堆顶方法，得再放回去
                heapq.heappush(heap, max_value)
        print(result)


nums = [1,3,-1,-3,5,3,6,7]
Solution(nums, 3).heap_large()
nums = [1]
Solution(nums, 1).heap_large()
